Embedded network systems typically have a limited memory capacity. Thus, the available memory must be used efficiently. In network receivers, for example, packets of various sizes are received over the network. Circular buffers (CBs) are often employed to efficiently store the received packets. Circular buffers read and write data sequentially. Generally, when packets arrive, they are stored in the circular buffer in the order of arrival. The sequential read property, however, makes it difficult for circular buffers to process packets that are not processed in sequence. For example, circular buffers are not able to directly process packets that arrive out-of-order or to process packets that are lost and recovered at a later time. Additional buffers are thus often employed with circular buffers to reorder packets after being read from a circular buffer.
Another buffer scheme is a Linked List Buffer (LLB). In LLBs, a fixed-size buffer is typically pre-allocated for incoming packets. Thus, the allocated size must be able to store the largest anticipated packet. Otherwise, packets exceeding the allocated size may be dropped. However, much of the allocated buffer space is wasted, as only a small portion of the stored packets require the full allocated size. Separate packets may be stored in different locations of an LLB, but are linked together. Thus, LLBs are a suitable candidate for applications requiring packet re-ordering.
A need exists for an improved buffer scheme that can dynamically allocate buffer space, while also being able to reorder packets.